#ifndef __QUEUE_H__
#define __QUEUE_H__

#include <sys/types.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "debug.h"

    
/******************************************************
 * ListNode
 ******************************************************/

template<class S>
class ListNode 
{
public:  
  S * data;
  ListNode * next, * prev;
};






/***********************************************************
 * Template Class: List
 ***********************************************************/

typedef enum 
  {
    LT_QUEUE = 0x90,
    LT_STACK,
  } ListType;

template<class T>
class List
{
private:
  ListNode<T> root;
  ListType type;
  ListNode<T> * ptr;
  int count;

public:
  List (ListType lt = LT_QUEUE) : 
    type (lt), ptr (NULL), count (0) { 
    this->root.next = &(this->root);
    this->root.prev = &(this->root);
  };
  ~List ()
  {
    ListNode<T> *p, *n;
    for (p = this->root.next; p != &(this->root); p = n)
      {
	n = p->next;
	delete p;
      }
  };
  
  void push (T * t);
  T * pop (void);
  T * alloc (void);

  // Foreach functions
  void feInit () { this->ptr = this->root.next; }
  void feNext () { assert (this->ptr); this->ptr = this->ptr->next; }
  bool feEnd () { assert (this->ptr); return (this->ptr == &(this->root)); }
  T * feGet () { assert (this->ptr); return this->ptr->data; }

  void attach (ListNode<T> * prev, ListNode<T> * node);
  void detach (ListNode<T> * node);

  int getCount () { return this->count; }
};


template<class T>
void List<T>::push (T * t)
{
  ListNode<T> * np = new ListNode<T> ();
  np->data = t;

  switch (this->type)
    {
    case LT_QUEUE: List::attach (this->root.prev, np); break;
    case LT_STACK: List::attach (this->root.next, np); break;
    default:
      assert (0);
    }

  this->count++;
  return ;
}

template<class T>
T * List<T>::pop (void)
{
  ListNode<T> * np ;
  T * t;

  if (&(this->root) == this->root.next)
    return NULL; 
  /* nothing to be returned */

  switch (this->type)
    {
    case LT_QUEUE: np = this->root.prev;  break;
    case LT_STACK: np = this->root.next;  break;
    default:
      assert (0);
    }

  List::detach (np);
  t = np->data;
  delete np;
  this->count--;
  return t;
}

template<class T>
T * List<T>::alloc (void)
{
  T * t = new T ();
  this->push (t);
  return t;
}

template<class T>
void List<T>::attach (ListNode<T> * prev, ListNode<T> * node)
{
  ListNode<T> * next = prev->next;
  node->next = next;
  node->prev = prev;
  prev->next = node;
  next->prev = node;
  return ;
}

template<class T>
void List<T>::detach (ListNode<T> * node)
{
  ListNode<T> * next = node->next;
  ListNode<T> * prev = node->prev;
  next->prev = prev;
  prev->next = next;
  node->next = NULL;
  node->prev = NULL;
  return ;
}




#endif /* __QUEUE_H__ */

